package com.Sequence.order;

import java.util.ArrayList;
import java.util.List;

public class MergeSort {
	public static void main(String[] args) {
		ArrayList<Integer> datas=new ArrayList<>();
		datas.add(9);
		datas.add(-16);
		datas.add(21);
		datas.add(23);
		datas.add(-30);
		datas.add(-49);
		datas.add(21);
		datas.add(30);
		datas.add(30);
		mergeSort(datas, 0, datas.size()-1);
		System.out.println(datas.toString());
	}
	
	public static void mergeSort(ArrayList<Integer> datas,int left,int right){
		
		if(left<right){
			int center=(left+right)/2;
			mergeSort(datas, left, center);
			mergeSort(datas, center+1, right);
			datas=merge(datas, left, center, right);
		}
	}
	
	public static ArrayList<Integer> merge(ArrayList<Integer> datas,int left,int center,int right){
		int len=datas.size();
		ArrayList<Integer> temps=(ArrayList<Integer>) datas.clone();
		int indexA,indexB,mid=center+1;
		indexA=left;
		indexB=mid;
		int i=left;
		while(indexA<=center&&indexB<=right){
			if(datas.get(indexA)<=datas.get(indexB)){
				temps.set(i++, datas.get(indexA++));
			}else {
				temps.set(i++, datas.get(indexB++));
			}
		}
		while(indexA<=center){
			temps.set(i++, datas.get(indexA++));
		}
		while (indexB<=right) {
			temps.set(i++, datas.get(indexB++));
		}
		while (left<=right) {
			datas.set(left, temps.get(left));
			left++;
		}
		return datas;
	}
}
